//给你一个整数数组 nums，请你将该数组升序排列。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 输入：nums = [5,2,3,1]
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 输入：nums = [5,1,1,2,0,0]
//输出：[0,0,1,1,2,5]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 50000 
// -50000 <= nums[i] <= 50000 
// 
// Related Topics 数组 分治 桶排序 计数排序 基数排序 排序 堆（优先队列） 归并排序 
// 👍 391 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func sortArray(nums []int) []int {
    quickSort(nums, 0, len(nums) - 1)

    return nums
}

func quickSort(nums []int, start, end int){
    if start >= end {
        return
    }

    l, r := start, end

    midVal := nums[(start + end) / 2]

    for l <= r {    // 为了后面遍历的时候 r在l前 分开两个分区 这里带=
        for nums[l] < midVal {     // 这里不能待=号  因为如果极端情况所有值都小于mid 会让数组越界
            l++
        }

        for nums[r] > midVal {
            r--
        }

        if l <= r {
            nums[l], nums[r] = nums[r], nums[l]
            l++
            r--
        }
    }

    quickSort(nums, start, r)
    quickSort(nums, l, end)
}
//leetcode submit region end(Prohibit modification and deletion)
